#include <stdio.h>
#include <stdlib.h>
#include <time.h>
#define N 1000

void fast_sort(int*,int,int);

int main(int argc,const char** argv)
{
  srand(time(NULL));
  clock_t start, end;
  double cpu_time_used;

  start = clock(); // 记录开始时间

  int *buf;
  buf = malloc(sizeof(int) * N);
  for (int i = 0; i < N; i++)
    buf[i] = rand() % N;

  fast_sort(buf,0,N - 1);
  end = clock(); // 记录结束时间

  cpu_time_used = ((double)(end - start)) / CLOCKS_PER_SEC; // 计算CPU时间
  printf("程序运行时间为 %f 秒\n", cpu_time_used);


  return 0;
}

void fast_sort(int* buf,int left,int right)
{
  if(left <= right)
    return;
  int i,j,key;
  i = left;
  j = right;
  key = buf[i];

  while(i < j)
  {
    while(i < j && buf[i] > key)
      j--;
    buf[i] = buf[j];
    while(i < j && buf[i] < key)
      i++;
    buf[j] = buf[i];
  }

  fast_sort(buf,left,i+1);
  fast_sort(buf,j + 1,right);
}
